package com.xiaoyu.arrays;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: DS_and_A
 * @description: 找出消失的数字
 * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
 * 请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
 *
 * 示例 1：
 * 输入：nums = [4,3,2,7,8,2,3,1]
 * 输出：[5,6]
 *
 * 进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
 *
 * @author: YuWenYi
 * @create: 2021-05-30 10:04
 **/
public class FindDisappearedNumbers_448 {

    //自己的解法,但是无法解决[1,1]答案却出现2的情况
    //因为自己理解错了题意,没看到n是数组长度,哎!!!,以为是数组中的最小值和最大值之间的缺失数
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) return res;
        Arrays.sort(nums);
        int min = nums[0];
        int max = nums[len - 1];
        for (int i = 0; i < len; i++) {
            if (min == nums[i]){
                min++;
            }else if (min > nums[i]){  //出现min大于num,只可能是出现重复数字了,因此需要把min减回来,并且保持i不动
                min--;
                i--;    //保持i不动
            }else {
                res.add(min);  //加了一个数后,min尝试++,但是i不能动,因为num[i]不知道比min大多少,需要一直循环
                min++;
                i--;   //因为这里i--,然后循环上又i++,所以这样能保持i不动
            }
            if (min > max){
                break;
            }
        }
        return res;
    }

    //官方题解
    public static List<Integer> findDisappearedNumbers1(int[] nums) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>();
        // 遍历数组，把值对应的下标加n,后续数组大于n的下标表示存在的值
        for (int num : nums) {
            // 计算出下标，因为是取余，所以就算这个位置之前有加过n，取余之后也不会影响原来的值，
            int mod = (num-1) % n;
            // 下标对应的值+n
            nums[mod] += n;
        }
        // 遍历数组，把没有出现过的数组添加到结果数组中
        for (int i = 0; i < n; i++) {
            // 因为存在的值都会加在对应数组下标上面加上n，所以肯定大于n
            if (nums[i] <= n){
                res.add(i+1);
            }
        }
        return res;
    }


    //方法三:原地哈希!!!
    public static List<Integer> findDisappearedNumbers2(int[] nums) {
        int len = nums.length;
        int i = 0;
        while (i < len){
            if (i+1 != nums[i]){
                int targetIndex = nums[i] - 1;
                if (nums[targetIndex] == nums[i]){
                    i++;
                    continue;
                }
                int temp = nums[i];
                nums[i] = nums[targetIndex];
                nums[targetIndex] = temp;
            }else {
                i++;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int j = 0; j < len; j++) {
            if (j + 1 != nums[j]){
                res.add(j+1);
            }
        }
        return res;
    }



    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2,4};
        System.out.println(findDisappearedNumbers2(nums));
    }
}
